package _2022.hot100._538_把二叉搜索树转换为累加树;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author： YHSimon
 * @date： 2022-06-12 15:35
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int num = 0;

    // 中序遍历就是从小到大，反过来就是从大到小
    public TreeNode convertBST2(TreeNode root) {
        if (root != null) {
            convertBST2(root.right);
            root.val += num;
            num = root.val;
            convertBST2(root.left);
        }
        return root;
    }


    // 3ms
    public TreeNode convertBST(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        inList(root, list);
        int[] sum = new int[list.size()];
        int tmp = 0;
        for (int i = 0; i < list.size(); i++) {
            tmp += list.get(i);
            sum[i] = tmp;
        }
        for (int i = 0; i < list.size(); i++) {
            map.put(list.get(i), tmp - sum[i] + list.get(i));
        }
        update(root, map);
        // System.out.println(list);
        return root;
    }

    public void inList(TreeNode root, List<Integer> list) {
        if (root != null) {
            inList(root.left, list);
            list.add(root.val);
            inList(root.right, list);
        }
    }

    public void update(TreeNode root, Map<Integer, Integer> map) {
        if (root != null) {
            update(root.left, map);
            root.val = map.get(root.val);
            update(root.right, map);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.convertBST(new TreeNode(4, new TreeNode(1, new TreeNode(0), new TreeNode(2, null, new TreeNode(3))), new TreeNode(6, new TreeNode(5), new TreeNode(7, null, new TreeNode(8))))));
    }
}
